240. Search a 2D Matrix II
Medium

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

 

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

 

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -109 <= matix[i][j] <= 109
  • All the integers in each row are sorted in ascending order.
  • All the integers in each column are sorted in ascending order.
  • -109 <= target <= 109
Accepted
463,054
Submissions
1,009,812
Seen this question in a real interview before?
Companies
Similar Questions

Average Rating: 4.72 (134 votes)

Premium

Solution


Approach 1: Brute Force

Intuition

As a baseline, we can search the 2D array the same way we might search an unsorted 1D array -- by examining each element.

Algorithm

The algorithm doesn't really do anything more clever than what is explained by the intuition; we loop over the array, checking each element in turn. If we find it, we return true. Otherwise, if we reach the end of the nested for loop without returning, we return false. The algorithm must return the correct answer in all cases because we exhaust the entire search space.

Complexity Analysis

  • Time complexity : O(nm)\mathcal{O}(nm)

    Becase we perform a constant time operation for each element of an n×mn\times m element matrix, the overall time complexity is equal to the size of the matrix.

  • Space complexity : O(1)\mathcal{O}(1)

    The brute force approach does not allocate more additional space than a handful of pointers, so the memory footprint is constant.


Intuition

The fact that the matrix is sorted suggests that there must be some way to use binary search to speed up our algorithm.

Algorithm

First, we ensure that matrix is not null and not empty. Then, if we iterate over the matrix diagonals, we can maintain an invariant that the slice of the row and column beginning at the current (row,col)(row, col) pair is sorted. Therefore, we can always binary search these row and column slices for target. We proceed in a logical fashion, iterating over the diagonals, binary searching the rows and columns until we either run out of diagonals (meaning we can return False) or find target (meaning we can return True). The binarySearch function works just like normal binary search, but is made ugly by the need to search both rows and columns of a two-dimensional array.

Complexity Analysis

  • Time complexity : O(log(n!))\mathcal{O}(\log(n!))

    It's not super obvious how O(log(n!))\mathcal{O}(\log(n!)) time complexity arises from this algorithm, so let's analyze it step-by-step. The asymptotically-largest amount of work performed is in the main loop, which runs for min(m,n)min(m, n) iterations, where mm denotes the number of rows and nn denotes the number of columns. On each iteration, we perform two binary searches on array slices of length mim-i and nin-i. Therefore, each iteration of the loop runs in O(log(mi)+log(ni))\mathcal{O}(\log(m-i)+\log(n-i)) time, where ii denotes the current iteration. We can simplify this to O(2log(ni))=O(log(ni))\mathcal{O}(2\cdot \log(n-i))=\mathcal{O}(\log(n-i)) by seeing that, in the worst case, nmn\approx m. To see why, consider what happens when nmn \ll m (without loss of generality); nn will dominate mm in the asymptotic analysis. By summing the runtimes of all iterations, we get the following expression:

    (1)O(log(n)+log(n1)+log(n2)++log(1)) (1) \quad \mathcal{O}(\log(n) + \log(n-1) + \log(n-2) + \ldots + \log(1))

    Then, we can leverage the log multiplication rule (log(a)+log(b)=log(ab)\log(a)+\log(b)=\log(ab)) to rewrite the complexity as:

    (2)O(log(n)+log(n1)+log(n2)++log(1))=O(log(n(n1)(n2)1))=O(log(1(n2)(n1)n))=O(log(n!)) \begin{aligned} (2) \quad \mathcal{O}(\log(n) + \log(n-1) + \log(n-2) + \ldots + \log(1)) &= \mathcal{O}(\log(n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 1)) \\ &= \mathcal{O}(\log(1 \cdot \ldots \cdot (n-2) \cdot (n-1) \cdot n)) \\ &= \mathcal{O}(\log(n!)) \end{aligned}

    Because this time complexity is fairly uncommon, it is worth thinking about its relation to the usual analyses. For one, log(n!)=O(nlogn)\log(n!) = \mathcal{O}(n\log n). To see why, recall step 1 from the analysis above; there are nn terms, each no greater than log(n)\log(n). Therefore, the asymptotic runtime is certainly no worse than that of an O(nlogn)\mathcal{O}(n\log n) algorithm.

  • Space complexity : O(1)\mathcal{O}(1)

    Because our binary search implementation does not literally slice out copies of rows and columns from matrix, we can avoid allocating greater-than-constant memory.


Approach 3: Divide and Conquer

Intuition

We can partition a sorted two-dimensional matrix into four sorted submatrices, two of which might contain target and two of which definitely do not.

Algorithm

Because this algorithm operates recursively, its correctness can be asserted via the correctness of its base and recursive cases.

Base Case

For a sorted two-dimensional array, there are two ways to determine in constant time whether an arbitrary element target can appear in it. First, if the array has zero area, it contains no elements and therefore cannot contain target. Second, if target is smaller than the array's smallest element (found in the top-left corner) or larger than the array's largest element (found in the bottom-right corner), then it definitely is not present.

Recursive Case

If the base case conditions have not been met, then the array has positive area and target could potentially be present. Therefore, we seek along the matrix's middle column for an index row such that matrix[row1][mid]<target<matrix[row][mid] matrix[row-1][mid] < target < matrix[row][mid] (obviously, if we find target during this process, we immediately return true). The existing matrix can be partitioned into four submatrice around this index; the top-left and bottom-right submatrice cannot contain target (via the argument outlined in Base Case section), so we can prune them from the search space. Additionally, the bottom-left and top-right submatrice are sorted two-dimensional matrices, so we can recursively apply this algorithm to them.

Complexity Analysis

  • Time complexity : O(nlogn)\mathcal{O}(n\log n)

    First, for ease of analysis, assume that nmn \approx m, as in the analysis of approach 2. Also, assign x=n2=matrixx=n^2=|matrix|; this will make the master method easier to apply. Now, let's model the runtime of the divide & conquer approach as a recurrence relation:

    T(x)=2T(x4)+x T(x) = 2 \cdot T(\frac{x}{4}) + \sqrt{x}

    The first term (2T(x4)2 \cdot T(\frac{x}{4})) arises from the fact that we recurse on two submatrices of roughly one-quarter size, while x\sqrt{x} comes from the time spent seeking along a O(n)O(n)-length column for the partition point. After binding the master method variables (a=2;b=4;c=0.5a=2;b=4;c=0.5) we notice that logba=c\log_b{a}=c. Therefore, this recurrence falls under case 2 of the master method, and the following falls out:

    T(x)=O(xclogx)=O(x0.5logx)=O((n2)0.5log(n2))=O(nlog(n2))=O(2nlogn)=O(nlogn) \begin{aligned} T(x) &= \mathcal{O}(x^c \cdot \log x) \\ &= \mathcal{O}(x^{0.5} \cdot \log x) \\ &= \mathcal{O}((n^2)^{0.5} \cdot \log(n^2)) \\ &= \mathcal{O}(n \cdot \log(n^2)) \\ &= \mathcal{O}(2n \cdot \log n) \\ &= \mathcal{O}(n \cdot \log n) \\ \end{aligned}

    Extension: what would happen to the complexity if we binary searched for the partition point, rather than used a linear scan?

  • Space complexity : O(logn)\mathcal{O}(\log n)

    Although this approach does not fundamentally require greater-than-constant addition memory, its use of recursion means that it will use memory proportional to the height of its recursion tree. Because this approach discards half of matrix on each level of recursion (and makes two recursive calls), the height of the tree is bounded by logn\log n.


Approach 4: Search Space Reduction

Intuition

Because the rows and columns of the matrix are sorted (from left-to-right and top-to-bottom, respectively), we can prune O(m)\mathcal{O}(m) or O(n)\mathcal{O}(n) elements when looking at any particular value.

Algorithm

First, we initialize a (row,col)(row, col) pointer to the bottom-left of the matrix.[1] Then, until we find target and return true (or the pointer points to a (row,col)(row, col) that lies outside of the dimensions of the matrix), we do the following: if the currently-pointed-to value is larger than target we can move one row "up". Otherwise, if the currently-pointed-to value is smaller than target, we can move one column "right". It is not too tricky to see why doing this will never prune the correct answer; because the rows are sorted from left-to-right, we know that every value to the right of the current value is larger. Therefore, if the current value is already larger than target, we know that every value to its right will also be too large. A very similar argument can be made for the columns, so this manner of search will always find target in the matrix (if it is present).

Check out some sample runs of the algorithm in the animation below:

Current
1 / 35

Complexity Analysis

  • Time complexity : O(n+m)\mathcal{O}(n+m)

    The key to the time complexity analysis is noticing that, on every iteration (during which we do not return true) either row or col is is decremented/incremented exactly once. Because row can only be decremented mm times and col can only be incremented nn times before causing the while loop to terminate, the loop cannot run for more than n+mn+m iterations. Because all other work is constant, the overall time complexity is linear in the sum of the dimensions of the matrix.

  • Space complexity : O(1)\mathcal{O}(1)

    Because this approach only manipulates a few pointers, its memory footprint is constant.

Footnotes


  1. This would work equally well with a pointer initialized to the top-right. Neither of the other two corners would work, as pruning a row/column might prevent us from achieving the correct answer. ↩︎

Report Article Issue

Comments: 79
JoyceYan's avatar
Read More

approach 4 is amazing!!!

456
Show 10 replies
Reply
Share
Report
anthhht's avatar
Read More

Isn't the binary search on the diagonals a bit silly? You can just run binary search on the rows, for each row, and time complexity is still O(n log n). Approach 4 is very cool though

168
Show 15 replies
Reply
Share
Report
black-penguin's avatar
Read More

Me after finished the binary search solution: "I am genius!!!"
Me after looking at the solution 4: "I am so noob!!!"

61
Show 1 reply
Reply
Share
Report
RogerFederer's avatar
Read More

I think vertical meaning is not correct in the solution. I changed it to following:

class Solution(object):
    def binary_search(self, matrix, target, start, vertical):
        lo = start
        hi = len(matrix)-1 if vertical else len(matrix[0])-1

        while hi >= lo:
            mid = (lo + hi)/2
            if not vertical: # searching a row
                if matrix[start][mid] < target:
                    lo = mid + 1
                elif matrix[start][mid] > target:
                    hi = mid - 1
                else:
                    return True
            else: # searching a column
                if matrix[mid][start] < target:
                    lo = mid + 1
                elif matrix[mid][start] > target:
                    hi = mid - 1
                else:
                    return True
        
        return False

    def searchMatrixBS(self, matrix, target):
        # an empty matrix obviously does not contain `target`
        if not matrix:
            return False

        for i in range(min(len(matrix), len(matrix[0]))):
            vertical_found = self.binary_search(matrix, target, i, True)
            horizontal_found = self.binary_search(matrix, target, i, False)
            if vertical_found or horizontal_found:
                return True
        
        return False

25
Show 4 replies
Reply
Share
Report
littledog's avatar
Read More

In Approach 3, Should it be 'searchRec(left, row, mid-1, down)' instead of 'searchRec(left, up, mid-1, down)'?? Otherwise you are recursing the 3/4 area of the original matrix...

18
Reply
Share
Report
haihaicode's avatar
Read More

can solution 4 be even faster, i.e. O(lg(m)+lg(n)), if use binary search to replace the one-step-by-one-step search?

6
Show 3 replies
Reply
Share
Report
pinkfloyda's avatar
Read More

In Approach 3: Divide and Conquer, the inner while loop can use binary search again, which will make the time complexity as lg(mn)

5
Show 3 replies
Reply
Share
Report
bsml's avatar
Read More

Thank you for these clear, diverse solutions! Would anyone mind verifying that the time complexity analysis for divide and conquer (sol 3) + binary search case is as follows:

Let x = n * m.
As shown by OP, T(x) = 2T(x/4) + log(x), due to binary search.
As shown by OP, x^(log of 2 base 4) = x^(1/2).
Since x^(1/2) is polynomially larger than log(x) (some discussion here: https://math.stackexchange.com/questions/1614848/meaning-of-polynomially-larger),
T(x) = O(x^(1/2)), by case 1 of master theorm.
Hence, if we substitute x with n * m, we get T = O((nm)^(1/2)), which is at most O(n), where n is larger of n and m.

3
Show 1 reply
Reply
Share
Report
jianh73's avatar
Read More

Another Divide and Conquer. Every time split the matrix into 4 parts. Using binary tree idea search idea in the 2D matrix. The complexity should be O(max(m,n)). Accepted solution as following:

class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length<=0 || matrix[0].length <=0)
{
return false;
}
return searchSubMatrix(matrix, target, 0, 0, matrix.length, matrix[0].length);
}

private boolean searchSubMatrix(int[][] matrix, int target, int startR, int startC, int rows,int columns)
{
    if(matrix[startR][startC] == target)
    {
        return true;
    }
    
    //the up left is the smallest item and bottom right is the largest one.
    if((columns <= 1 && rows <= 1) 
       || !((matrix[startR+rows-1][startC + columns-1]>= target)&&(matrix[startR][startC]<=target)))
    {
        return false;    
    }
    int newRows = rows/2+rows%2;
    int newColumns = columns/2+columns%2;
    return searchSubMatrix(matrix, target, startR, startC, newRows, newColumns)
        || searchSubMatrix(matrix, target, startR + rows/2, startC, newRows, newColumns)
        || searchSubMatrix(matrix, target, startR + rows/2, startC+columns/2, newRows, newColumns)
        || searchSubMatrix(matrix, target, startR, startC+columns/2, newRows, newColumns);
}

}

3
Show 1 reply
Reply
Share
Report
milky_la's avatar
Read More

#3 Divide and Conquer: it looks like the description (and time analysis) are wrong. The code splits the input matrix into three, not four. The first matrix is double the size: x/2, not x/4. One matrix is dropped..searchRec(left, up, mid-1, down) || searchRec(mid+1, up, right, row-1); Am i missing something?

Also looks like that row iteration can be avoided: even split, check to choose between first two or the 4th matrix .. then would have constant const instead of sqrt(x) factor in each recursion

2
Show 1 reply
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/01/2021 12:30Accepted164 ms14.7 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.